package leetcode_core.leetcode_1;

import java.util.Arrays;

public class CountPrimes {
    public int countPrimes(int n) {
        boolean[] isPrime = new boolean[n];
        //将数组都初始化为true
        Arrays.fill(isPrime,true);
        //素数从2开始算起
        for(int i = 2;i*i<=n;i++){
            if(isPrime[i]){
                //i的倍数不可能再是素数了
                for(int j = i*i;j<n;j+=i){
                    isPrime[j]=false;
                }
            }
        }
        int count = 0;
        for(int i = 2;i<n;i++){
            if(isPrime[i]){
                count++;
            }
        }
        return count;
    }


}
